package cn.good.yan.sf.t4;

/**
 * 4 递归
 * 算法- 冒泡排序
 * 算法- 插入排序
 *
 * @author shengren.yan
 * @create 2024-05-12
 */
public class Demo2 {

    public static void sort(int[] arr) {
        // 算法- 冒泡排序 - 1 数组：5 4 3 2 1
//        f1(arr, arr.length - 1);
        // 算法- 冒泡排序 - 2 数组：5 4 3 2 1
//        f2(arr, arr.length - 1);
        // 算法- 插入排序 - 1 数组 4 3 2 1
        f3(arr, 1);
    }


    // 算法- 冒泡排序 - 1 数组：5 4 3 2 1
    public static void f1(int[] arr, int j) {
        if (j == 0) {
            return;
        }
        for (int i = 0; i < j; i++) {
            if (arr[i] > arr[i + 1]) {
                int t = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = t;
            }
        }
//        System.out.println(arr);
        System.out.println("---");
        f1(arr, j - 1);
    }

    // 算法- 冒泡排序 - 2 数组：5 4 3 2 1  - 设置一个中介值-判断最小的边界
    public static void f2(int[] arr, int j) {
        if (j == 0) {
            return;
        }
        int num = 0;
        for (int i = 0; i < j; i++) {
            if (arr[i] > arr[i + 1]) {
                int t = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = t;
                num = i;
            }
        }
//        System.out.println(arr);
        System.out.println("---");
        f2(arr, num);
    }

    // 算法- 插入排序 - 1 数组 4 3 2 1  / 3 4 2 1
    public static void f3(int[] arr, int low) {
        if (low == arr.length) {
            return;
        }
        // 已排序的 i 、 未排序的下标（low）
        int t = arr[low]; // 未排序当前对象
        int i = low - 1;

        while (i >= 0 && arr[i] > t) {
            // 没有找到位置就一直循环
            arr[i + 1] = arr[i];
            i--;
        }
        arr[i + 1] = t; // 找到位置了
//        System.out.println(arr);
        f3(arr, low + 1);
    }

    public static void main(String[] args) {
        // 演示：冒泡排序 - 方式1
//        int[] arr1 = {5, 4, 3, 2, 1};
//        sort(arr1);
//        System.out.println(arr1);

        // 演示：冒泡排序 - 方式2  - 设置一个中介值-判断最小的边界
//        int[] arr2 = {3, 2, 1, 4, 5};
//        sort(arr2);
//        System.out.println(arr2);
        // f2 方式 打印2次 ---  f1 打印4次 --- （f2 比 f1 方式 少循环次数）

        // 演示：插入排序 - 方式1
        int[] arr3 = {4, 3, 2, 1};
        sort(arr3);
        System.out.println(arr3);

    }

}
